package cn.datastruct.three;

/*
    转化为稀疏数组：
        1.0代表为空数据
        2.求出数组的row,col以及不为0(count)的个数
        3.定义一个SparseArray[count+1][3]的数组，第一行存放row,col,count
        4.遍历原始二维数组找出数据不为0的数据，并记录位置和数值到SparseArray
        5.打印稀疏数组

    转化为二维数组：
        1.根据稀疏数组的第一行建立一个二维数组
        2.遍历把稀疏数组中的数据填充到对应二维数组位置
        3.遍历二维数组
*/
public class SparseArray {
    public static void main(String[] args) {

        //1.初始化原数组
        int[][] arr = new int[9][9];
        arr[1][3] = 4;
        arr[2][4] = 3;
        arr[3][3] = 10;
        arr[3][6] = 1;
        arr[5][4] = 8;

        //2.求出数组的row,col以及不为0(count)的个数
        int count = 0;
        for (int[] ints : arr) {
            for (int anInt : ints) {
                if (anInt != 0) {
                    count++;
                }
            }
        }

        //3.定义一个SparseArray[count+1][3]的数组，第一行存放row,col,count
        int[][] SparceArray = new int[count + 1][3];
        SparceArray[0][0] = arr.length;
        SparceArray[0][1] = arr[0].length;
        SparceArray[0][2] = count;
        //4.遍历原始二维数组找出数据不为0的数据，并记录位置和数值到SparseArray
        System.out.println("二维数组转化为稀疏数组");
        count = 1;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if (arr[i][j] != 0) {
                    SparceArray[count][0] = i;
                    SparceArray[count][1] = j;
                    SparceArray[count][2] = arr[i][j];
                    count++;
                }
            }

        }

        //5.打印稀疏数组
        for (int[] ints : SparceArray) {
            System.out.printf("%d\t%d\t%d\n", ints[0], ints[1], ints[2]);
        }

        //转化为二维数组：
        //1.根据稀疏数组的第一行建立一个二维数组
        int[][] Arr = new int[SparceArray[0][0]][SparceArray[0][1]];

        //2.遍历把稀疏数组中的数据填充到对应二维数组位置
        for (int i = 1; i < SparceArray.length; i++) {
            Arr[SparceArray[i][0]][SparceArray[i][1]] = SparceArray[i][2];
        }
        System.out.println("-----------------------");
        System.out.println("稀疏数组转化为二维数组");
        //3.遍历二维数组
        for (int[] ints : Arr) {
            for (int anInt : ints) {
                System.out.printf("%d\t", anInt);
            }
            System.out.println();

        }
    }

}

